/**
 * @file   Graph.h
 * @author Shao <student@student>
 * @date   Sat Dec 25 19:53:39 2021
 * 
 * @brief  
 * 
 * 
 */

#include <bits/stdc++.h>
using namespace std;

/*
 * 记录起点到每个顶点的最短路径的信息
 */
struct Distance {
  string path;
  int value;
  bool visit;
  Distance() {
      visit = false;
      value = 0;
      path = "";
  }
};

class Graph {
private:
  /*
   *  图的顶点个数
   */
  int vexnum;
  /*
   * 图的边数
   */
  int edge;
  /*
   * 邻接矩阵
   */
  int **arc;
  /*
   * 各个顶点最短路径的信息
   */   
  Distance * distance;
public:
  Graph(int vexnum, int edge);
  ~Graph();
  /*
   * 判断我们输入的的边是否合法
   */
  bool check_edge_value(int start, int end, int weight);
  /*
   * 创建图
   */
  void createGraph();
  /*
   * 打印邻接矩阵
   */
  void print();
  /*
   * 求最短路径
   */
  void Dijkstra(int begin);
  /*
   * 打印最短路径
   */
  void print_path(int);
};
Graph::Graph(int vexnum, int edge) {
  /*
   * 初始化顶点数与边数
   */
  this->vexnum = vexnum;
  this->edge = edge;
  /*
   * 创建邻接矩阵
   */
  arc = new int*[this->vexnum];
  distance = new Distance[this->vexnum];
  for (int i = 0; i < this->vexnum; i++) {
      arc[i] = new int[this->vexnum];
      for (int k = 0; k < this->vexnum; k++) {
              arc[i][k] = INT_MAX;     //邻接矩阵初始赋值均为无穷大
      }
  }
}
Graph::~Graph() {
  delete[] distance;
  for (int i = 0; i < this->vexnum; i++) {
      delete this->arc[i];
  }
  delete arc;
}

/*
 * 判断输入的边的信息是否合法
 */
bool Graph::check_edge_value(int start, int end, int weight) {
  if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {
      return false;
  }
  return true;
}

void Graph::createGraph() {
  cout << "请输入每条边的顶点1和顶点2以及其权重" << endl;
  int start;
  int end;
  int weight;
  int count = 0;
  while (count != this->edge) {
      cin >> start >> end >> weight;
      /*
       * 判断边的信息是否合法
       */
      while (!this->check_edge_value(start, end, weight)) {
          cout << "输入的边的信息不合法，请重新输入" << endl;
          cin >> start >> end >> weight;
      }
      /*
       * 对邻接矩阵赋值
       */
      arc[start - 1][end - 1] = weight;
      ++count;
  }
}

void Graph::print() {
  cout << "图的邻接矩阵为:" << endl;
  /*
   * 打印行
   */
  int count_row = 0;
  /*
   * 打印列
   */
  int count_col = 0;
  while (count_row != this->vexnum) {
      count_col = 0;
      while (count_col != this->vexnum) {
          if (arc[count_row][count_col] == INT_MAX)
              cout << "∞" << " ";
          else
          cout << arc[count_row][count_col] << " ";
          ++count_col;
      }
      cout << endl;
      ++count_row;
  }
}
void Graph::Dijkstra(int begin){
  /*
   * 初始化distance数组
   */
  int i;
  for (i = 0; i < this->vexnum; i++) {
      /*
       * 设置当前的路径
       */
      distance[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1);
      distance[i].value = arc[begin - 1][i];
  }
  /*
   * 设置起点到起点的路径为0
   */
  distance[begin - 1].value = 0;
  distance[begin - 1].visit = true;

  int count = 1;
  /*
   * 求剩余顶点的最短路径
   */
  while (count != this->vexnum) {
      int temp = 0;     //当前distance数组中最小的下标
      int min = INT_MAX;     //当前的最小值
      for (i = 0; i < this->vexnum; i++) {
        if (!distance[i].visit && distance[i].value < min)
        {
          min = distance[i].value;
          temp = i;
        }
      }
      /*
       * 把temp对应的顶点加入到已经找到的最短路径的集合中
       */
      distance[temp].visit = true;
      ++count;
      for (i = 0; i < this->vexnum; i++) {
          if (!distance[i].visit && arc[temp][i] != INT_MAX && (distance[temp].value + arc[temp][i]) < distance[i].value)
          {
            /*
             * 更新最短路径与长度
             */
            distance[i].value = distance[temp].value + arc[temp][i];
            distance[i].path = distance[temp].path + "-->v" + to_string(i + 1);
          }
      }
  }

}
void Graph::print_path(int begin) {
  string str;
  str = "v" + to_string(begin);
  cout << "以" << str << "为起点的图的最短路径为:" << endl;
  for (int i = 0; i != this->vexnum; i++) {
    if (distance[i].value != INT_MAX)
      cout << distance[i].path << "=" << distance[i].value << endl;
      else {
          cout << distance[i].path << "是无最短路径的" << endl;
      }
  }
}
